package developer.算法.贪心算法.跳跃游戏;

/**
 * @author zhangyongkang
 * @time 2025/4/8 14:33
 * @description 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * <p>
 * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [2,3,1,1,4]
 * 输出：true
 * 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
 * 示例 2：
 * <p>
 * 输入：nums = [3,2,1,0,4]
 * 输出：false
 * 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 104
 * 0 <= nums[i] <= 105
 */
public class JumpGame {
    public static void main(String[] args) {
        Solution3 solution = new Solution3();
        System.out.println(solution.canJump(new int[]{2, 3, 1, 1, 4}));
        System.out.println(solution.canJump(new int[]{3, 2, 1, 0, 4}));
    }

    static class Solution3 {


        public boolean canJump(int[] nums) {
            int maxJump = nums[0];//当前节点最大的跳跃距离
            for (int i = 1; i < nums.length; i++) {
                if (maxJump <= 0) {
                    return false;
                }
                maxJump = Math.max(maxJump - 1, nums[i]);
            }
            return true;
        }
    }


    static class Solution {
        public boolean canJump(int[] nums) {
            int currentMaxJump = 1;
            for (int i = 0; i < nums.length; i++) {
                if (i == nums.length - 1) {
                    return currentMaxJump > 0;
                }
                if (currentMaxJump == 0) {
                    break;
                }
                int num = nums[i];
                currentMaxJump = Math.max(currentMaxJump - 1, num);
            }
            return false;
        }
    }

    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/jump-game/solutions/203549/tiao-yue-you-xi-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public class SolutionOfficial {
        public boolean canJump(int[] nums) {
            int n = nums.length;
            int rightmost = 0;
            for (int i = 0; i < n; ++i) {
                if (i <= rightmost) {
                    rightmost = Math.max(rightmost, i + nums[i]);
                    if (rightmost >= n - 1) {
                        return true;
                    }
                }
            }
            return false;
        }
    }


}
